package com.db.collections;

import java.io.Externalizable;

public class IntHashMap {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int DEFAULT_BUCKET_VOLUME = 2;
    
    transient int size;
    int threshold;
    final float loadFactor;
    
    // Maximal count of values that can be hold for one key
    int bucketVolume;
    
    int[] table;
    int[] bucketInfo;
    
    public IntHashMap() {
    	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    public IntHashMap(int initialCapacity) {
    	this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public IntHashMap(int initialCapacity, float loadFactor) {
    	if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        bucketVolume = DEFAULT_BUCKET_VOLUME;
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new int[capacity * bucketVolume];
        bucketInfo = new int[capacity];
    }
    
    final int hash(int k) {
        int h = k;

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
	public int get(int key) throws KeyNotFoundException {
		int hash = hash(key);
        int initIndex = indexFor(hash, bucketInfo.length);
        int offset = bucketInfo[initIndex];
        for (int i = initIndex * bucketVolume; i < initIndex * bucketVolume + offset; i += 2) {
            if (table[i] == key)
                return table[i + 1];
        }

    	throw new KeyNotFoundException(String.format("Could not find value by key %d%n", key));
	}
	
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    
    public boolean containsKey(int key) {
		int hash = hash(key);
        int initIndex = indexFor(hash, bucketInfo.length);
        int offset = bucketInfo[initIndex];
        for (int i = initIndex * bucketVolume; i < initIndex * bucketVolume + offset; i += 2) {
            if (table[i] == key)
                return true;
        }
        
        return false;
    }
	
	public void put(int key, int value) {
		int hash = hash(key);
        int initIndex = indexFor(hash, bucketInfo.length);
        int offset = bucketInfo[initIndex];
        for (int i = 0; i < offset; i += 2) {
            if (table[initIndex * bucketVolume + i] == key) {
                table[initIndex * bucketVolume + i + 1] = value;
                return;
            }
        }
        
        addEntry(hash, key, value, initIndex);
	}
	
	void addEntry(int hash, int key, int value, int bucketIndex) {
        if ((size >= threshold) && (bucketInfo[bucketIndex] != 0)) {
            resize(2 * bucketInfo.length);
            hash = hash(key);
            bucketIndex = indexFor(hash, bucketInfo.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
	
    void createEntry(int hash, int key, int value, int bucketIndex) {
        int offset = bucketInfo[bucketIndex];
        if (offset >= bucketVolume) {
        	{
                resize(2 * bucketInfo.length);
                hash = hash(key);
                bucketIndex = indexFor(hash, bucketInfo.length);
            }

            createEntry(hash, key, value, bucketIndex);
        } else {
	        table[bucketIndex * bucketVolume + offset] = key;
	        table[bucketIndex * bucketVolume + offset + 1] = value;
	    	bucketInfo[bucketIndex] += 2;
	        size++;
        }
    }
    
    void resize(int newCapacity) {
        int[] oldTable = table;
        int oldCapacity = bucketInfo.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        int[] newTable = new int[newCapacity * bucketVolume];
        int[] newBucketInfo = new int[newCapacity];
        for (int i=0; i<newBucketInfo.length; i++)
        	newBucketInfo[i] = 0;
        
        transfer(newTable, newBucketInfo);
        table = newTable;
        bucketInfo = newBucketInfo;
        
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    void transfer(int[] newTable, int[] newBucketInfo) {   
    	for (int i=0; i<bucketInfo.length; i++) {
    		int offset = bucketInfo[i];
    		for (int j = i * bucketVolume; j < i * bucketVolume + offset; j += 2) {
    			int hash = hash(table[j]);
                int initIndex = indexFor(hash, newBucketInfo.length);
                int newOffset = newBucketInfo[initIndex];
                newTable[initIndex * bucketVolume + newOffset] = table[j];
                newTable[initIndex * bucketVolume + newOffset + 1] = table[j + 1];
                newBucketInfo[initIndex] += 2;
    		}
        }
    }
	
	public int remove(int key) throws KeyNotFoundException {        
        int hash = hash(key);
        int initIndex = indexFor(hash, bucketInfo.length);
        int offset = bucketInfo[initIndex];
        int fromIndex = offset;
        int value = 0;
        for (int i = 0; i < offset; i += 2) {
            if (table[initIndex * bucketVolume + i] == key) {
            	fromIndex = initIndex * bucketVolume + i + 2;
            	value = table[initIndex * bucketVolume + i + 1];
            	break;
            }
        }
        if (fromIndex == offset)
        	throw new KeyNotFoundException(String.format("Could not find value by key %d%n", key));
        
        for (int i = fromIndex; i < initIndex * bucketVolume + offset; i++) {
        	table[fromIndex - 2] = table[fromIndex];
        }
        table[initIndex * bucketVolume + offset - 2] = 0;
        table[initIndex * bucketVolume + offset - 1] = 0;
        bucketInfo[initIndex] -= 2;

        return value;
	}
    
    public void clear() {
        int[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = 0;
        size = 0;
        int[] buckets = bucketInfo;
        for (int i=0; i<buckets.length; i++)
        	buckets[i] = 0;
    }
}
